package src.leetcode.dp.hard_0123;

public class maxProfit {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxProfit(new int[]{6,5,4,8,6,8,7,8,9,4,5}));
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;

        /*
         * 定义 5 种状态:
         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];

        for (int i = 1; i < len; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }

        return dp[len - 1][4];
    }
}



//class Solution {
//    public int maxProfit(int[] prices) {
//        int []diff = new int[prices.length - 1];
//        for (int i = 0; i < prices.length - 1; i++) {
//            diff[i] = prices[i + 1] - prices[i];
//        }
//
//        int []ranges = new int[2];
//        ranges[1] =  diff.length;
//        int max1 = maxdiff(diff, ranges);
//        if(max1 == 0) return 0;
//        int max2 = maxdiff(diff, new int[]{0, ranges[0]});
//        int max3 = maxdiff(diff, new int[]{ranges[1], diff.length});
//        if(max2 == 0 && max3 == 0) {
//            for (int i = ranges[0]; i < ranges[1]; i++){
//                diff[i] = -diff[i];
//            }
//            int max4 = maxdiff(diff, new int[]{ranges[0], ranges[1]});
//            return max1 + max4;
//        }
//        return max1 + Math.max(max2, max3);
//    }
//
//    private int maxdiff(int[] diff, int[] ranges){
//        int left = ranges[0];
//        int right = ranges[1];
//        int sum = 0;
//        int max = 0;
//        int i = left;
//        int j = left;
//
//        while (j < right){
//            sum += diff[j++];
//            if(sum > max) {
//                ranges[0] = i;
//                ranges[1] = j;
//                max = sum;
//            }
//            if(sum < 0) {
//                i = j;
//                sum = 0;
//            }
//        }
//        return max;
//    }
//}
